#include <iostream>
#include <unordered_map>
#include <list>

class LRUCache {
private:
    int capacity;//缓存容量
    std::list<std::pair<int, int>> cacheList;//双链表的添加和删除操作都不需要移动元素,但是需要辅助O1找到操作对象   
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> cacheMap;   //根据key找到映射关系地址   

public:
    LRUCache(int cap) : capacity(cap) {}

    int get(int key) {
        auto it = cacheMap.find(key);
        if (it == cacheMap.end()) {
            return -1;
        }
        // 把该元素移到链表头部，表示最近使用
        std::pair<int, int> kv = *(it->second);
        //获取映射关系后就删除掉
        cacheList.erase(it->second);
        //将映射关系头插
        cacheList.push_front(kv);
        //维护映射关系
        cacheMap[key] = cacheList.begin();
        return kv.second;
    }

    void put(int key, int value) {
        //check值是存在
        auto it = cacheMap.find(key);
        if (it != cacheMap.end()) {
            // 若 key 已存在，更新其值并移到链表头部
            cacheList.erase(it->second);
        }
        else if (cacheList.size() == capacity) {
            // 若缓存已满，淘汰链表尾部元素（最久未使用）
            int lastKey = cacheList.back().first;
            cacheMap.erase(lastKey);//删除哈希表中的值
            cacheList.pop_back();//从链表中去掉
        }
        // 插入新元素到链表头部
        cacheList.push_front({ key, value });
        //维护映射关系
        cacheMap[key] = cacheList.begin();
    }
};
